1. Field of the Invention
The present invention is in the field of data-packet processing and forwarding over a data-packet-network, and pertains particularly to methods and apparatus for aggregating physical links between routers into one or more virtual interfaces, and manipulating such aggregations according to a hierarchical data structure.
2. Discussion of the State of the Art
The growth and development of the public network known as the Internet is a very well-known phenomenon. The Internet has grown very rapidly both in terms of end users and content providers. This phenomenal growth has generated a great need for improved hardware and software for handling the greatly increased data traffic.
Hardware-software systems known as routers are the workhorses of the Internet. In current art most routers are capable of handling traffic at rates in the gigabit per second range. The present inventors are engaged in developing Terrabit network routers, and in proposing and developing solutions for problems inherent in current art routing systems.
As is well-known in the art, there are several different kinds of packets to be routed in Internet traffic. One type of packet is termed in the art an IP packet. IP packets can be used for all-types of data; including Internet telephony and Internet video streaming. IP packets have header fields defining such as the source and destination for each packet.
In the art of packet routing it is well-known that it is desirable for packets to arrive at a destination in the same order that they were generated at a source. For one reason, out-of-order packets may well cause dropouts in applications such as voice and video communication and the like. Provision may well be made at a destination to re-order packets, but such re-ordering is expensive in processor resources. Such provision is commonly not made, and packets may be lost or discarded in any case.
If there were to be only one hop from a source to a destination, this would not be problem. Since there are invariably several machines through which packets must pass and be processed, and because newer and better routers may employ processing parallelism, attention must be paid to the order of packets.
The packets handled by a router can be logically divided into flows, where each flow is the set of all packets, which are being sent from the same origin to the same destination. A group of such flows can be treated as a single flow. Generally speaking, if packets in the same flow are always sent from every system in the order that they were received, the original ordering will be honored.
A method is known to the inventor for internal routing of a packets received in a packet router. The method comprises steps of selecting a logical interface having multiple physical ports as a destination for the packet, processing any one or more addresses or labels of the packet and other packets received by a common function, producing thereby results unique to the packets in which the addresses and labels processed differ, and then mapping the physical ports at the destination to the unique results produced by processing the addresses or labels of packets, and finally routing the data packet according to the computed mapping. Weighting is applied to the physical ports in the mapping scheme, the weighting reflecting different transmission capacities of the physical ports.
The Internet network is divided logically into various standard layers of differing hardware and software functionality. In consulting one standard and well-known layering protocol termed Open System Interconnection (OSI). There are, according to this scheme, seven distinct network layers. Network layers amount to separated levels of network function. The well-known International Organization for Standardization (ISO) and the International Telecommunication Union-Telecommunication Standardization Sector (ITU-T) brought about the OSI architecture. Specific details regarding protocols and functions associated with OSI layers are published and available. The focus of this specification concentrates on function of two of the lower layers pertinent to the present invention.
The two layers of most concern in establishing physical data links and logical routing interfaces are layers 2 and 3. Layer 2 controls the physical layer or layer 1 data flow. Layer 2 is responsible for establishing link connections between workstations. Layer 3 addresses and routes packets. Layer 3 is responsible for such as addressing and control functions. Layer 3 manages routing function including packet switching, routing, data congestion, and translation of logical addresses to physical addresses. There are also other known and standardized architectures defining different numbers and descriptions of network layers. Among these architectures however, layers 1-3 are essentially alike in their functions and what attributes of network communication they are responsible for among the most standardized of architectures.
It is known to the inventor that a plurality of physical interfaces (ports) of a router may be logically bound together or aggregated to form a bond. A bond as known to the inventor is defined as an aggregation of layer 2 link addresses, which share a single layer 3 address and are considered in terms of layer 3 protocols as a logical or virtual interface. For example, two or more separate communication lines of a router can be seen in the network layer 3 as one large trunk. One advantage of establishing a bond is that layer 3 is not aware whether a given logical address defined in layer 3 is an aggregation of layer 2 links or is simply a single physical address. In this way, layer 3 protocol only has to consider a single logical address for routing purposes, and does not need to table every physical link address aggregated under the layer 3 address. As a result, routing is more efficient. The lowest layer (1) resolves all address hierarchies into a same-level list of physical interfaces or ports.
It has occurred to the inventor that more efficiency in routing could be achieved with respect to creating bonds comprising multiple router links by introducing a concept of hierarchy concerning bond assignment as well as flexibility of assignment and manipulation of bonds and bond structures.
Therefore, what is clearly needed is a method for creating and managing bonds that enables more hardware-controlled processing, less software-controlled processing, and provides more administrative flexibility with respect to changing bond assignments. A method such as this would make Layer 3 processing more efficient and improve load-balancing capability in data routing.